#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;

//template<class T>
//class vector
//{
//	T& operator[](int i)
//	{
//		assert(i < _size);
//		return _a[i];
//	}
//
//private:
//	T* _a;
//	size_t _size;
//	size_t capacity;
//};
//
//class vector
//{
//	int& operator[](int i)
//	{
//		assert(i < _size);
//		return _a[i];
//	}
//private:
//	int* _a;
//	size_t _size;
//	size_t _capacity;
//};
////void test()
////{
////	vector<int> v1;
////
////	vector<int> v2(10, 1);
////	vector<int> v3(++v2.begin(), --v2.end());
////
////	for (size_t i = 0; i < v3.size(); i++)
////	{
////		cout << v3[i] << " ";
////	}
////		cout << endl;
////
////	vector<int>::iterator it = v3.begin();
////	while (it != v3.end())
////	{
////		cout << *it << " ";
////		++it;
////	}
////	cout << endl;
////
////	for (auto ch : v3)
////	{
////		cout << ch << " ";
////	}
////}
////
////void test1()
////{
////	vector<int> v1;
////
////	vector<int> v2(10, 1);
////	vector<int> v3(++v2.begin(), --v2.end());
////
////	v2.resize(5);
////
////}
////
////void test2()
////{
////	vector<int> v(10, 1);
////     
////	for (auto ch : v)
////	{
////		cout << ch << " ";
////	}
////	cout << endl;
////
////	v.insert(v.begin(), 2);
////	for (auto ch : v)
////	{
////		cout << ch << " ";
////	}
////	cout << endl;
////
////	v.push_back(2);
////	for (auto ch : v)
////	{
////		cout << ch << " ";
////	}
////	cout << endl;
////
////	v.insert(v.begin()+3, 5);
////	for (auto ch : v)
////	{
////		cout << ch << " ";
////	}
////	cout << endl;
////
////
////	vector<int> a(5, 2);
////	vector<vector<int>> vv(10, a);
////	vv[2][1] = 1;
////}
////void test3()
////{
////	vector<int> b(5, 2);
////	vector<vector<int>> bb(10, b);
////	for (size_t i = 0; i < bb.size(); i++)
////	{
////		for (size_t j = 0; j < bb[i].size(); j++)
////		{
////			cout << bb[i][j]<<" ";
////		}
////		cout << endl;
////	}
////	cout << endl;
////}
////int main()
////{
////	test3();
////	return 0;
////}

//class Solution {
//public:
//    vector<vector<int>> generate(int numRows) {
//		vector<vector<int>> vv(numRows);
//		for (int i = 0; i < numRows; i++)
//		{
//			vv[i].resize(i + 1, 1);
//		}
//		for (size_t i = 2; i < vv.size(); i++)
//		{
//			for (size_t j = 1; j < vv[i].size()-1; j++)
//			{
//				vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
//			}
//		}
//		return vv;
//    }
//};

namespace bit {
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        void reverse(size_t n)
        {
            if (n > capacity())
            {
                size_t oldsize = size();
                T* tmp = new T[n];
                memcpy(tmp, _start, size() * sizeof(T));
                delete[] _start;

                _start = tmp;
                _finish = _start + oldsize;
                _end_of_storage = _start + n;
            }
        }

        size_t size() {
            return _finish - _start;
        }

        size_t capacity() {
            return _end_of_storage - _start;
        }

        bool empty()
        {
            return _start == _finish;
        }

        void pop_back()
        {
            assert(!empty);
            --_finish;
        }
        iterator begin()const
        {
            return _start;
        }

        iterator end()const
        {
            return _finish;
        }
        T& operator[](size_t i)
        {
            assert(i < size());
            return _start[i];
        }
        const T& operator[](size_t i)const
        {
            assert(i < size());
            return _start[i];
        }
        void insert(iterator pos, const T& x)
        {

            if (_finish == _end_of_storage)
            {
                reverse(capacity() == 0 ? 4 : capacity() * 2);
            }
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = x;
            ++_finish;
        }
        void push_back(const T& x)
        {
            if (_finish == _end_of_storage)
            {
                reverse(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }
        template <class T>
        void print_vector(const vector<T>& v)
        {
            typename vector<int>::iterator it = v.begin();

            while (it != v.end())
            {
                cout << *it << " ";
                ++it;
            }
            cout << endl;

            for (auto e : v)
            {
                cout << e << " ";
            }
            cout << endl;
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };

    void Test_vector1()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        //for (size_t i = 0; i < v.size(); i++)
        //{
        //    cout << v[i] << " ";
        //}
        //cout << endl;
        //vector<int>::iterator it = v.begin();

    }

    void Test_vector2()
    {
        vector<int> vb;
        vb.push_back(1);
        vb.push_back(2);
        vb.push_back(3);
        vb.push_back(4);
        vb.push_back(5);

        vb.print_vector(vb);
        vb.insert(vb.begin() + 2, 30);
        vb.print_vector(vb);

    }


}
